package main.Q901_1000;

import java.util.Stack;

public class Q921_930 {
    public static void main(String[] args) {
        System.out.println("Question921：使括号有效的最少添加");
        System.out.println("Question922：按奇偶排序数组 II");
        int[] arr = new int[]{4, 5, 2, 7};
        System.out.println(new Question922().sortArrayByParityII(arr));
        System.out.println("Question923：");
        System.out.println("Question924：");
        System.out.println("Question925：");
        System.out.println("Question926：将字符串翻转到单调递增");
        System.out.println("Question927：");
        System.out.println("Question928：");
        System.out.println("Question929：");
        System.out.println("Question930：");
    }
}

class Question921 {
    public int minAddToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] str = s.toCharArray();
        for (int i = 0; i < str.length; i++) {
            if (stack.isEmpty() || stack.peek() == ')') stack.push(str[i]);
            else if (stack.peek() == '(' && str[i] == '(') stack.push(str[i]);
            else if (stack.peek() == '(' && str[i] == ')') stack.pop();
        }
        return stack.size();
    }
}

class Question922 {
    public int[] sortArrayByParityII(int[] nums) {
        int i = 0, j = 1;
        int[] result = new int[nums.length];
        for (int k = 0; k < nums.length; k++) {
            if (nums[k] % 2 == 0) {
                result[i] = nums[k];
                i += 2;
            } else {
                result[j] = nums[k];
                j += 2;
            }
        }
        return result;
    }
}

class Question926 {
    public int minFlipsMonoIncr(String s) {
        int length = s.length();
        char[] str = s.toCharArray();
        int[][] dp = new int[length][2];
        for (int i = 0; i < length; i++) {
            if (i == 0) {
                dp[i][0] = str[i] == '0' ? 0 : 1;
                dp[i][1] = str[i] == '1' ? 0 : 1;
            } else {
                dp[i][0] = dp[i - 1][0] + (str[i] == '0' ? 0 : 1);
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + (str[i] == '1' ? 0 : 1);
            }
        }
        return Math.min(dp[length - 1][0], dp[length - 1][1]);
    }
}